#ifndef _0A4EB75C_F5B5_4832_BFC9_A55E6B0BBEEF_BINARYTREE
#define _0A4EB75C_F5B5_4832_BFC9_A55E6B0BBEEF_BINARYTREE
/*
Author: Shakti Prasad Misra
License: GPL2
Revesion: 0.1v
All usage of this file is permitted, for free software or commercial. 
But the Author name should not be changed. If changes are done please add it to the changed section.
*/
#include <memory>
#include <string>
#include <cmath>
#include "../../Utils/DOTFileHandler.h"
#include "../common/GeneralNode.h"

#define MODULE "TreesAndGraphs"

#ifdef BINARYTREE_FILE_VERSION_
#undef BINARYTREE_FILE_VERSION_
#endif
#define BINARYTREE_FILE_VERSION_ "0.1"

using namespace std;

namespace tng
{

enum LinkType
{
    eP = 0,//Parent
    eL = 1,//Left Child
    eR = 2,//Right Child
    eN = 3 //Any invalid Link
};

enum ErrorCodes
{
    eSUCCESS = 0,
    eERROR_ALLOC_FAILED = 1,
    eERROR_NULL_VAL_PASSED = 2,
    eFAILED
};

//Node trait class Start ========================
template <typename nodeIDType>
class nodeTrait
{
private:
    unsigned long int _weight;//Number of times same element is added to the tree
    unsigned long int _nodeHeight;
    nodeIDType _nodeID;

public:
    nodeTrait(nodeIDType& id):_weight(1), _nodeHeight(0), _nodeID(id)
    {}

    void setWeight(unsigned long int weight)//sets weight
    {
        _weight = weight;
    }

    void wtPP()//Increment weight by one
    {
        ++_weight;
    }

    void setHeight(unsigned long int height)//sets height
    {
        _nodeHeight = height;
    }

    void htPP()//Increment height by one
    {
        ++_nodeHeight;
    }

    unsigned long int getHeight()
    {
        return _nodeHeight;
    }

    unsigned long int getWeight()
    {
        return _weight;
    }

    const nodeIDType& getNodeID()const
    {
        return _nodeID;
    }

    void setNodeID(nodeIDType& id)
    {
        _nodeID = id;
    }
};
//Node trait class end ========================
typedef nodeTrait<unsigned long int> binNodeTrait;

//BinaryTree class start ========================
template<typename keyType, 
typename dataType, 
typename BinaryTreeAllocator = std::allocator<BinTreeNode> 
>
class BinaryTree
{
    typedef TreeNode<keyType, 
        dataType, 
        binNodeTrait/*traits*/, 
        1/*maxKeys*/, 
        3/*maxNodes = maxKeys + 1*/> BinTreeNode;

//Defines for this class
#define _keyval _keyVal[0]
#define _parent _nodes[eP]
#define _left   _nodes[eL]
#define _right  _nodes[eR]

private:
    /*
    template <typename keyValType,
    typename dataType,
    typename nodeIDType,
    typename traits,
    unsigned long int maxKeys,
    unsigned long int maxNodes = maxKeys + 1>
    */
    BinTreeNode* _head,
        *_current;
    unsigned long int _nodeCount;
    unsigned long int _height;
    unsigned long int _totalNodes;
    BinaryTreeAllocator _allocator;
    string _errString;
#ifdef VIZ
    visualize _viz;
#endif

private://Node manipulation

public://Constructor and destructor
    BinaryTree():_nodeCount(0), 
        _height(0), 
        _totalNodes(0)
#ifdef VIZ
        ,
        _viz("test.dot")
#endif
    {
        _head = NULL;//Null tree
        _current = NULL;
#ifdef VIZ
        _viz.init();
#endif
    }

    BinaryTree(dataType data, keyType key):_nodeCount(0), 
        _height(0), 
        _totalNodes(1)
#ifdef VIZ
        ,
        _viz("test.dot")
#endif
    {
        initializeNode(&_head, data, key);
        _current = _head;
#ifdef VIZ
        _viz.init();
#endif
    }

    ~BinaryTree()
    {
        if(_head)
        {
            delete _head;
        }

#ifdef VIZ
        _viz.commit();
#endif
    }

private:
    ErrorCodes initializeNode(BinTreeNode** node, dataType& data, keyType& key)
    {
        *node = _allocator.allocate(1);

        if(node && *node)
        {
            //new ( (void *) node ) BinTreeNode  ( ++_nodeCount );
            (*node)->_keyval = key;
            (*node)->_parent = 0;
            (*node)->_left = 0;
            (*node)->_right = 0;
            (*node)->_data = data;
            (*node)->_traits.setNodeID(++_nodeCount);
            return eSUCCESS;
        }

        *node = NULL;
        return eERROR_ALLOC_FAILED;
    }

    ErrorCodes addNodeToTree(BinTreeNode* Node);
    ErrorCodes addNodeToNode(BinTreeNode* toNode, BinTreeNode* Node);

public://Methods of the BinaryTree class
    ErrorCodes initTree(dataType& data, keyType& key)
    {
        return initializeNode(&_head, data, key);
    }

    ErrorCodes createNAddNode(dataType& data, keyType& key)
    {
        BinTreeNode* node = NULL;
        if(eSUCCESS != initializeNode(&node, data, key))
            return eFAILED;
        return addNodeToTree(node);
    }

    BinaryTree& operator++()
    {
        if(true == _skipChildren)
        {
            //_current->_nodes[] TODO
        }
    }

public://Iterators of the BinaryTree class

//Foreward declarations start
    class Iterator_Sibling;
    class Iterator_Base;
    class Iterator_Traverse;
//Foreward declarations end

//=======================================

//Iterator_Base start
    class Iterator_Base
    {
    protected:
        BinTreeNode* _start,
                     _current;//Do not change order of declaration
        bool _skipChildren;

    public:
          Iterator_Base():
              _start(0),
              _current(0),
              _skipChildren(false)
          {
          }

          Iterator_Base(const BinTreeNode* node):
              _start(node),
              _current(node),
              _skipChildren(false)
          {
          }

          Iterator_Base(const Iterator_Base& val):
              _start(val._start),
              _current(val._start),
              _skipChildren(false)
          {
          }

          dataType& operator*()
          {
              return _current->_data;
          }

        dataType* operator->()
        {
            return &(_current->_data);
        }

        const dataType& operator*()const
        {
            return _current->_data;;
        }

        const dataType* operator->()const
        {
            return &(_current->_data);
        }

        virtual ~Iterator_Base()
        {
        }

        void skipChildren(const bool val = true)
        {
            _skipChildren = val;
        }

        virtual unsigned long int childrenCount() = 0;

        virtual Iterator_Sibling begin_sibling()
        {
            if(NULL != _current->_nodes[eP])
            {
                Iterator_Sibling ret(_current->_nodes[eP]->_nodes[eL]);
                return ret;
            }
            return end();
        }

        virtual Iterator_Sibling end_sibling()
        {
            return Iterator_Sibling(0);
        }

        bool operator!=(Iterator_Base& val)
        {
            if(_current =! val.getCur_ptr())
                return true;

            return false;
        }

        const BinTreeNode* getCur_ptr()const
        {
            return _current;
        }

    };
//Iterator_Base end

//=======================================

//Iterator_Sibling start
    class Iterator_Sibling : public Iterator_Base
    {
    private:
        LinkType _eCurNode;
        bool _isPostOp;
    public:
        Iterator_Sibling(const BinTreeNode* node):
              _start(node), 
              _current(node),
              _curNode(eL),
              _isPostOp(false)
        {
        }

        Iterator_Sibling(const Iterator_Base& node):
            _start(node._start),
            _current(_start),
            _curNode(eL),
            _isPostOp(false)
        {
        }

        ~Iterator_Sibling()
        {
        }
    public:
        Iterator_Sibling& operator++()
        {
            switch(_eCurNode)
            {
            case eL:
                _eCurNode = eR;
                break;
            case eR:
                _eCurNode = eL;
                break;
            case eP:
            default:
                return Iterator_Sibling(0);
                //Error
            }

            _current = _start[eP]->_nodes[_eCurNode];
            _isPostOp = false;

            return *this;
        }

        Iterator_Sibling& operator++(int)
        {
            switch(_eCurNode)
            {
            case eL:
                _eCurNode = eR;
                _current;//TODO
                break;
            case eR:
                _eCurNode = eL;
                break;
            case eP:
            default:
                return Iterator_Sibling(0);
                //Error
            }

            _isPostOp = true;

            return *this;
        }

        Iterator_Sibling& operator--(int)
        {
            return this->operator++(666);
        }

        Iterator_Sibling& operator--()
        {
            return this->operator++();
        }

        dataType& operator*()
        {
            return *operator->();//Calling one function to keep changes localized.
        }

        dataType* operator->()
        {
            if(true == _isPostOp)
            {
                _current = _current->_nodes[eP]->_nodes[_eCurNode];
                _isPostOp = false;
            }

            return &(_current->_data);
        }
    };
//Iterator_Sibling end

//=======================================

//Iterator_Traverse start
    class Iterator_Traverse:public Iterator_Base
    {
    public:
        enum traversalOrder
        {
            ePREORDER = 0,
            ePOSTORDER = 1,
            eINORDER = 2
        };
    private:
        bool _postOrderDone;
        bool _preOrderDone;
        traversalOrder _trOrder;
        BinTreeNode* _prevNode;
        LinkType _lastLinkType;
    private:
    public:

        Iterator_Traverse():
          _start(0), 
              _current(0), 
              _skipChildren(false),
              _trType(eITERATIVE),
              _trOrder(ePREORDER),
              _prevNode(NULL)
        {
        }

        Iterator_Traverse(const BinTreeNode* node):
        _start(node), 
            _current(node), 
            _skipChildren(false),
            _trType(eITERATIVE),
            _trOrder(ePREORDER),
            _prevNode(NULL)
        {
        }

        Iterator_Traverse(const Iterator_Base& val):
        _start(val._start), 
            _current(val._start), 
            _skipChildren(false),
            _trType(eITERATIVE),
            _trOrder(ePREORDER),
            _prevNode(NULL)
        {
        }

        void setTraversalOrder(traversalOrder val)
        {
            _trOrder = val;
        }

        traversalOrder getTraversalOrder()const
        {
            return _trOrder;
        }

        bool empty()
        {
            return NULL == _start? true : false;
        }

        bool hasNext()
        {
            if(NULL == _current)
                return false;

            return true;
        }

        Iterator_Traverse& operator++()//Preorder traversal only
        {
            if(!_start || !_current)
            {
                return *this;//Continue
            }

            if(true == _preOrder\
                Done)
            {
                if(NULL != _current->_nodes[eL])
                {
                    _current = _current->_nodes[eL];
                }
                elif(NULL != _current->_nodes[eL])
                {
                    _current = _current->_nodes[eR];
                }
                elif(NULL != _current->_nodes[eP])
                {
                    _current = _current->_nodes[eP];
                }
            }

            _preOrderDone = true;

            return *this;
        }

        Iterator_Traverse& operator++(int)//Postorder traversal only
        {
            if(!_start || !_current)
            {
                return Iterator_Traverse();//Continue
            }

            _postOrderDone = true;
            BinTreeNode* temp = _current, *prevTemp = temp;
            while(temp)
            {
                if(temp->_nodes[eL])
                {
                    temp = temp->_nodes[eL];
                    _lastLinkType = eL;
                }
                elif(temp->_nodes[eR])
                {
                    temp = temp->_nodes[eR];
                    _lastLinkType = eR;
                }
                else
                    prevTemp = temp->_nodes[eP];
                    break;
            }

            return *temp;
        }

        dataType& operator*()
        {
            if(_preOrderDone && _prevNode)
            {
                return _prevNode->data;
            }

            return NULL != _current? _current->_data : dataType(0);
        }

        dataType* operator->()
        {
            if(_preOrderDone && _prevNode)
            {
                return &(_prevNode->_data);
            }

            return NULL != _current? &(_current->_data) : NULL;
        }
    };
//Iterator_Traverse End

//=======================================

};//BinaryTree class end ========================

template<typename keyType, typename dataType, typename BinaryTreeAllocator>
ErrorCodes BinaryTree<keyType, dataType, BinaryTreeAllocator>::addNodeToNode(BinTreeNode* toNode, BinTreeNode* Node)
{
    if(!Node && !toNode)
    {
        return eERROR_NULL_VAL_PASSED;
    }

    while(toNode->_left && toNode->_right)
    {
        if(Node->_keyval < toNode->_keyval)
            toNode = toNode->_left;
        elif( Node->_keyval > toNode->_keyval)
            toNode = toNode->_right;
        else
        {
            toNode->_traits.wtPP();
            break;
        }
    }

    if(!toNode->_left)
        toNode->_left = Node;
    else
        toNode->_right = Node;

#ifdef VIZ
    char buffer [33] = {0};
    _viz.gwrite("*fr *to", _itoa(toNode->_traits.getNodeID(), buffer, 10), _itoa(Node->_traits.getNodeID(), buffer, 10) );
#endif

    return eSUCCESS;
}

template<typename keyType, typename dataType, typename BinaryTreeAllocator>
ErrorCodes BinaryTree<keyType, dataType, BinaryTreeAllocator>::addNodeToTree(BinTreeNode* Node)
{
    return addNodeToNode(_head, Node);
}










}//namespace BT end

#endif //_0A4EB75C_F5B5_4832_BFC9_A55E6B0BBEEF_BINARYTREE







